// 二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。
// 实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

// 返回转换后的单向链表的头节点。单链表升序


// dummy用于连接表头，然后用prev去调整指针
struct TreeNode *dummy, *prev;

void helper(struct TreeNode* root) {
    if (root == NULL) return ;
    // 中序遍历
    helper(root->left);
    if (prev == NULL) {  // 递归到最左边， 第一个节点
        prev = root;
        dummy->right = root;       
    } else {
        prev->right = root; // prev仍指向原节点，root回溯到其它节点
        prev = root;
    }
    root->left = NULL;
    helper(root->right);
}

struct TreeNode* convertBiNode(struct TreeNode* root){
    if (root == NULL) return NULL;
    dummy = malloc(sizeof(struct TreeNode)); 
    prev = NULL;
    helper(root);
    return dummy->right;
}